// 322. 零钱兑换

function coinChange(coins: number[], amount: number): number {
  // 加一是因为掠过0
  const dp: number[] = new Array(amount + 1).fill(amount + 1);
  dp[0] = 0;
  // console.log(dp)
  for (let i = 1; i <= amount; i++) {
    // 外层是计算的钱的数量
    for (let j = 0; j < coins.length; j++) {
      // 内层循环硬币
      if (coins[j] <= i) {
        // 如果硬币小于目标值
        // 减去硬币面额之后找dp数值 +1 在比较两个大小 硬币有不同的面额 找到最小的方案
        dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
        // console.log(dp[i]);
      }
    }
  }
  // console.log(dp);
  return dp[amount] > amount ? -1 : dp[amount];
}

// // 279. 完全平方数
// 思路完全一致 导致有点懵逼
const coins = [1, 2, 5],
  amount = 11;
console.log(coinChange(coins, amount));
